\documentclass{article}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage{wrapfig}
\usepackage{amsmath}
\geometry{  rmargin=1in
           ,lmargin=1in
           ,tmargin=1in
           ,bmargin=1in
         }

\begin{document}

\begin{flushright}
   Dennis Castleberry
\\ Sudip Biswas
\\ Prof. R. Kannan
\\ CSC 7103: 001
\\ 06 October 2011
\end{flushright}

\begin{center}
Simplified Multi-Threaded Web Server Using PThreads
\end{center}

Our multi-threaded web server is coded in C/C++ and uses the pthreads library
for threading along with X11 libraries for graphical output.
The server utilizes three input files. The first is for requests, and contains
for each entry the IP address of the client, a client-side timestamp of the
request, whether the request is GET or PUT, and the name of the requested file.
The second contains a tree representing the directory structure of the files to
be served and their local document identifiers $[0..n]$. The third contains a
permissions table with local document identifiers, IP addresses along with the
permissions granted to them (0 for read, 1 for write, 2 for read/write). A
mutex lock is placed upon the permissions table and directory structure files
when writing to them, as occurs in the case of PUT requests. 

The server makes use of five types of threads. A dispatcher thread reads
requests line by line from the request input file, stores the request into a
string buffer, and passes the buffer to a resolver thread. One of $N$ resolver
threads then locates the requsted file in the directory structure file; upon
failure, it passes an error message to the GUI thread and exits, and upon
success, it passes the request data to an authentication thread. The
authentication thread checks the permissions table for the permissions the IP
has to the requested file; if it has the proper permission, it adds the job to
a queue, and if not, it passes an error message to the GUI thread and exits.
Worker threads created at start time accept jobs in FIFO order from the job
queue. The worker threads create GUI threads which print the file name and
exit. When finished processing one job, a worker thread accepts another. The
GUI threads use X11 libraries to print a given message, be it an error message
or file name, to an X window.  See Figure 1 for the thread workflow diagram.

\begin{wrapfigure}{r}{0.5\textwidth}
 \begin{center}
  \includegraphics[width=0.48\textwidth]{workflow.png}
 \end{center}
 \caption{Workflow of the server.}
\end{wrapfigure}

Our request data structure is used to hold data required by the resolver and
authentication threads (IP, filename, type of request, local document
identifier, authorization flag). There are $N$ request data structures for each
of $N$ resolver and authentication threads. The request data structure contains
an integer which indicates the state of the resolver thread (working,
finished).  Before a request is read from the input file, the dispatcher checks
the status of each thread via the state variable; if the state of a given
thread is set to finished, the dispatcher thread creates another resolver
thread using the ID of that thread. This allows for concurrence of the resolver
threads. See Figure 2 for a possible scenario involving $N=3$
concurrently-running resolver threads.

We make use of two important classes: queue and cache. The queue class
contains data required by the worker threads to process given requests: the IP
address, type of request, file name, and timestamp. The queue is instantiated
within the dispatcher thread before the requests are read. For each request
read from the input file, the dispatcher pushes the request information onto
the queue. During this time, a mutex lock is held on the queue size, which is
incremented upon a push operation; as do concurrent worker threads, which
decrement the queue size upon completing the handling of the request. Worker
threads also hold locks on the tail index. 

\begin{wrapfigure}{l}{0.5\textwidth}
 \begin{center}
  \includegraphics[width=0.48\textwidth]{possible.png}
 \end{center}
 \caption{Worker and resolver threads run concurrently.}
\end{wrapfigure}

The cache class contains a circular array along with methods for updating the
array upon retrieval of a file (i.e. the local document identifier) according
to the LRU caching algorithm. The last file to be retrieved is placed at the
head of the array, and all other files are arranged in order behind it.  In
this way, the least-recently used element is always located at the tail of the
array.  Upon retrieval of an item not in the cache, that item replaces the
tail-item in the array and is moved to the head of the array. The caching
thread is called by a worker thread before outputting the file contents via the
GUI thread.

In summary, by using a shared data structure which maintains thread status
information, our multi-threaded file server allows for the concurrent running
of resolver-authenticator and worker-GUI threads to process file server
requests in FIFO order, utilizing the LRU algorithm for efficient cache
management, successfully printing the requested information to screen.

\end{document}
